#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_OP 10
#define KEY(n) (n ? n->key : -1)

typedef struct Node{
    int key;
    Node *lchild, *rchild;
} Node;

Node *getNewNode(int key){
    Node *p = (Node *)malloc(sizeof(Node));
    p->key = key;
    p->lchild = p->rchild = NULL;
    return p;
}

Node *insert(Node *root, int key) {
    if (root == NULL) return getNewNode(key);
    if (key == root->key) return root;
    if (key < root->key) root->lchild = insert(root->lchild, key);
    else root->rchild = insert(root->rchild, key);
    return root;
}

void clear(Node *root){
    if(root == NULL) return;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return;
}

Node *predecessor(Node *root) {
    Node *tmp = root->lchild;
    while(tmp->rchild) tmp = tmp->rchild;
    return tmp;
}

Node *erase(Node *root, int key){
    if(root == NULL) return root;
    if(key < root->key) root->lchild = erase(root->lchild, key);
    else if(key > root->key) root->rchild = erase(root->rchild, key);
    else{
        if(root->lchild == NULL && root->rchild == NULL){
            free(root);
            return NULL;
        }else if(root->lchild == NULL || root->rchild == NULL){
            Node *tmp = root->lchild ? root->lchild : root->rchild;
            free(root);
            return tmp;
        }else{
            Node *tmp = predecessor(root);
            root->key = tmp->key;
            root->lchild = erase(root->lchild, tmp->key);
        }
    }
    return root;
}

void output(Node *root) {
    if(root == NULL) return;
    printf("(%d ; %d; %d)\n", KEY(root), KEY(root->lchild), KEY(root->rchild));
    output(root->lchild);
    output(root->rchild);
    return;
}

void in_order(Node *root) {
    if(root == NULL) return;
    in_order(root->lchild);
    printf("%d ", root->key);
    in_order(root->rchild);
    return;
}

int main(){
    srand(time(0));
    Node *root = NULL;
    for(int i = 0; i < MAX_OP; i++){
        int key = rand() % 100;
        printf("insert key %d to BST\n", key);
        root = insert(root, key);
    }
    output(root);
    printf("in order: ");
    in_order(root);
    printf("\n");
    printf("input a erase number:\n");
    int x;
    while(~scanf("%d", &x)){
        if(x == -1) break;
        printf("erase %d from BST\n", x);
        root = erase(root, x);
        in_order(root);
        printf("\n");
    }
    clear(root);

    return 0;
}
